Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time
Identifieur interne : 000661 ( Main/Exploration ); précédent : 000660; suivant : 000662Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time
Auteurs : Seunghwa Kang [États-Unis] ; Jijun Tang [États-Unis] ; Stephen W. Schaeffer [États-Unis] ; David A. Bader [États-Unis]Source :
- PLoS ONE [ 1932-6203 ] ; 2011.
Abstract
Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious evolutionary scenario using the species' genome data. MP methods are considered to be accurate, but they are also computationally expensive especially for a large number of species. Several disk-covering methods (DCMs), which decompose the input species to multiple overlapping subgroups (or disks), have been proposed to solve the problem in a divide-and-conquer way.
We design a new DCM based on the spectral method and also develop the
Url:
DOI: 10.1371/journal.pone.0022483
PubMed: 21887219
PubMed Central: 3160844
Affiliations:
- États-Unis
- Caroline du Sud, Géorgie (États-Unis), Pennsylvanie
- University Park (Pennsylvanie)
- Université d'État de Pennsylvanie
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000643
- to stream Pmc, to step Curation: 000643
- to stream Pmc, to step Checkpoint: 000480
- to stream Ncbi, to step Merge: 000258
- to stream Ncbi, to step Curation: 000258
- to stream Ncbi, to step Checkpoint: 000258
- to stream Main, to step Merge: 000663
- to stream Main, to step Curation: 000661
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time</title><author><name sortKey="Kang, Seunghwa" sort="Kang, Seunghwa" uniqKey="Kang S" first="Seunghwa" last="Kang">Seunghwa Kang</name><affiliation wicri:level="2"><nlm:aff id="aff1"><addr-line>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia</wicri:regionArea><placeName><region type="state">Géorgie (États-Unis)</region></placeName></affiliation></author><author><name sortKey="Tang, Jijun" sort="Tang, Jijun" uniqKey="Tang J" first="Jijun" last="Tang">Jijun Tang</name><affiliation wicri:level="2"><nlm:aff id="aff2"><addr-line>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina</wicri:regionArea><placeName><region type="state">Caroline du Sud</region></placeName></affiliation></author><author><name sortKey="Schaeffer, Stephen W" sort="Schaeffer, Stephen W" uniqKey="Schaeffer S" first="Stephen W." last="Schaeffer">Stephen W. Schaeffer</name><affiliation wicri:level="4"><nlm:aff id="aff3"><addr-line>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">University Park (Pennsylvanie)</settlement></placeName><orgName type="university">Université d'État de Pennsylvanie</orgName></affiliation></author><author><name sortKey="Bader, David A" sort="Bader, David A" uniqKey="Bader D" first="David A." last="Bader">David A. Bader</name><affiliation wicri:level="2"><nlm:aff id="aff4"><addr-line>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia</wicri:regionArea><placeName><region type="state">Géorgie (États-Unis)</region></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">21887219</idno><idno type="pmc">3160844</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3160844</idno><idno type="RBID">PMC:3160844</idno><idno type="doi">10.1371/journal.pone.0022483</idno><date when="2011">2011</date><idno type="wicri:Area/Pmc/Corpus">000643</idno><idno type="wicri:Area/Pmc/Curation">000643</idno><idno type="wicri:Area/Pmc/Checkpoint">000480</idno><idno type="wicri:Area/Ncbi/Merge">000258</idno><idno type="wicri:Area/Ncbi/Curation">000258</idno><idno type="wicri:Area/Ncbi/Checkpoint">000258</idno><idno type="wicri:Area/Main/Merge">000663</idno><idno type="wicri:Area/Main/Curation">000661</idno><idno type="wicri:Area/Main/Exploration">000661</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time</title><author><name sortKey="Kang, Seunghwa" sort="Kang, Seunghwa" uniqKey="Kang S" first="Seunghwa" last="Kang">Seunghwa Kang</name><affiliation wicri:level="2"><nlm:aff id="aff1"><addr-line>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia</wicri:regionArea><placeName><region type="state">Géorgie (États-Unis)</region></placeName></affiliation></author><author><name sortKey="Tang, Jijun" sort="Tang, Jijun" uniqKey="Tang J" first="Jijun" last="Tang">Jijun Tang</name><affiliation wicri:level="2"><nlm:aff id="aff2"><addr-line>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina</wicri:regionArea><placeName><region type="state">Caroline du Sud</region></placeName></affiliation></author><author><name sortKey="Schaeffer, Stephen W" sort="Schaeffer, Stephen W" uniqKey="Schaeffer S" first="Stephen W." last="Schaeffer">Stephen W. Schaeffer</name><affiliation wicri:level="4"><nlm:aff id="aff3"><addr-line>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">University Park (Pennsylvanie)</settlement></placeName><orgName type="university">Université d'État de Pennsylvanie</orgName></affiliation></author><author><name sortKey="Bader, David A" sort="Bader, David A" uniqKey="Bader D" first="David A." last="Bader">David A. Bader</name><affiliation wicri:level="2"><nlm:aff id="aff4"><addr-line>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line></nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia</wicri:regionArea><placeName><region type="state">Géorgie (États-Unis)</region></placeName></affiliation></author></analytic><series><title level="j">PLoS ONE</title><idno type="eISSN">1932-6203</idno><imprint><date when="2011">2011</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p>Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious evolutionary scenario using the species' genome data. MP methods are considered to be accurate, but they are also computationally expensive especially for a large number of species. Several disk-covering methods (DCMs), which decompose the input species to multiple overlapping subgroups (or disks), have been proposed to solve the problem in a divide-and-conquer way.</p><p>We design a new DCM based on the spectral method and also develop the <italic>COGNAC</italic> (Comparing Orders of Genes using Novel Algorithms and high-performance Computers) software package. <italic>COGNAC</italic> uses the new DCM to reduce the phylogenetic tree search space and selects an output tree from the reduced search space based on the MP principle. We test the new DCM using gene order data and inversion distance. The new DCM not only reduces the number of candidate tree topologies but also excludes erroneous tree topologies which can be selected by original MP methods. Initial labeling of internal genomes affects the accuracy of MP methods using gene order data, and the new DCM enables more accurate initial labeling as well. <italic>COGNAC</italic> demonstrates superior accuracy as a consequence. We compare <italic>COGNAC</italic> with FastME and the combination of the state of the art DCM (Rec-I-DCM3) and GRAPPA . <italic>COGNAC</italic> clearly outperforms FastME in accuracy. <italic>COGNAC</italic> –using the new DCM–also reconstructs a much more accurate tree in significantly shorter time than GRAPPA with Rec-I-DCM3.</p></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Fitch, Wm" uniqKey="Fitch W">WM Fitch</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hartigan, Ja" uniqKey="Hartigan J">JA Hartigan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author><author><name sortKey="Wyman, S" uniqKey="Wyman S">S Wyman</name></author><author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name></author><author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name></author><author><name sortKey="Yan, M" uniqKey="Yan M">M Yan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Fertin, G" uniqKey="Fertin G">G Fertin</name></author><author><name sortKey="Labarre, A" uniqKey="Labarre A">A Labarre</name></author><author><name sortKey="Rusu, I" uniqKey="Rusu I">I Rusu</name></author><author><name sortKey="Tannier, E" uniqKey="Tannier E">E Tannier</name></author><author><name sortKey="Vialette, S" uniqKey="Vialette S">S Vialette</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Huson, Dh" uniqKey="Huson D">DH Huson</name></author><author><name sortKey="Nettles, Sm" uniqKey="Nettles S">SM Nettles</name></author><author><name sortKey="Warnow, Tj" uniqKey="Warnow T">TJ Warnow</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Huson, Dh" uniqKey="Huson D">DH Huson</name></author><author><name sortKey="Vawter, L" uniqKey="Vawter L">L Vawter</name></author><author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Roshan, Uw" uniqKey="Roshan U">UW Roshan</name></author><author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author><author><name sortKey="Williams, Tl" uniqKey="Williams T">TL Williams</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mohar, B" uniqKey="Mohar B">B Mohar</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Von Luxburg, U" uniqKey="Von Luxburg U">U von Luxburg</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hendy, Md" uniqKey="Hendy M">MD Hendy</name></author><author><name sortKey="Penny, D" uniqKey="Penny D">D Penny</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bergsten, J" uniqKey="Bergsten J">J Bergsten</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author><author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name></author><author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lin, Y" uniqKey="Lin Y">Y Lin</name></author><author><name sortKey="Rajan, V" uniqKey="Rajan V">V Rajan</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name></author><author><name sortKey="Wang, Ls" uniqKey="Wang L">LS Wang</name></author><author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Stewart, Ca" uniqKey="Stewart C">CA Stewart</name></author><author><name sortKey="Almes, Gt" uniqKey="Almes G">GT Almes</name></author><author><name sortKey="Wheeler, Bc" uniqKey="Wheeler B">BC Wheeler</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Coghlan, A" uniqKey="Coghlan A">A Coghlan</name></author><author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name></author><author><name sortKey="Oliver, Sg" uniqKey="Oliver S">SG Oliver</name></author><author><name sortKey="Paterson, Ah" uniqKey="Paterson A">AH Paterson</name></author><author><name sortKey="Stein, L" uniqKey="Stein L">L Stein</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Coghlan, A" uniqKey="Coghlan A">A Coghlan</name></author><author><name sortKey="Wolfe, Kh" uniqKey="Wolfe K">KH Wolfe</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bhutkar, A" uniqKey="Bhutkar A">A Bhutkar</name></author><author><name sortKey="Schaeffer, Sw" uniqKey="Schaeffer S">SW Schaeffer</name></author><author><name sortKey="Russo, Sm" uniqKey="Russo S">SM Russo</name></author><author><name sortKey="Xu, M" uniqKey="Xu M">M Xu</name></author><author><name sortKey="Smith, Tf" uniqKey="Smith T">TF Smith</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author><author><name sortKey="Siepel, Ac" uniqKey="Siepel A">AC Siepel</name></author><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name></author><author><name sortKey="Liu, T" uniqKey="Liu T">T Liu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Sankoff, D" uniqKey="Sankoff D">D Sankoff</name></author><author><name sortKey="El Mabrouk, N" uniqKey="El Mabrouk N">N El-Mabrouk</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bourque, G" uniqKey="Bourque G">G Bourque</name></author><author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Atteson, K" uniqKey="Atteson K">K Atteson</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Saitou, N" uniqKey="Saitou N">N Saitou</name></author><author><name sortKey="Nei, M" uniqKey="Nei M">M Nei</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, G" uniqKey="Li G">G Li</name></author><author><name sortKey="Ma, J" uniqKey="Ma J">J Ma</name></author><author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Pattengale, Nd" uniqKey="Pattengale N">ND Pattengale</name></author><author><name sortKey="Swenson, Km" uniqKey="Swenson K">KM Swenson</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Pothen, A" uniqKey="Pothen A">A Pothen</name></author><author><name sortKey="Simon, H" uniqKey="Simon H">H Simon</name></author><author><name sortKey="Liou, Kp" uniqKey="Liou K">KP Liou</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Newman, Mej" uniqKey="Newman M">MEJ Newman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name></author><author><name sortKey="Moret, Bm" uniqKey="Moret B">BM Moret</name></author><author><name sortKey="Yan, M" uniqKey="Yan M">M Yan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lin, Y" uniqKey="Lin Y">Y Lin</name></author><author><name sortKey="Moret, Bm" uniqKey="Moret B">BM Moret</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Arndt, W" uniqKey="Arndt W">W Arndt</name></author><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bernt, M" uniqKey="Bernt M">M Bernt</name></author><author><name sortKey="Merkle, D" uniqKey="Merkle D">D Merkle</name></author><author><name sortKey="Middendorf, M" uniqKey="Middendorf M">M Middendorf</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Swenson, Km" uniqKey="Swenson K">KM Swenson</name></author><author><name sortKey="To, Y" uniqKey="To Y">Y To</name></author><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wei Xu, A" uniqKey="Wei Xu A">A Wei Xu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name></author><author><name sortKey="Kunisawa, T" uniqKey="Kunisawa T">T Kunisawa</name></author><author><name sortKey="Sankoff, D" uniqKey="Sankoff D">D Sankoff</name></author></analytic></biblStruct></listBibl></div1></back></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Caroline du Sud</li><li>Géorgie (États-Unis)</li><li>Pennsylvanie</li></region><settlement><li>University Park (Pennsylvanie)</li></settlement><orgName><li>Université d'État de Pennsylvanie</li></orgName></list><tree><country name="États-Unis"><region name="Géorgie (États-Unis)"><name sortKey="Kang, Seunghwa" sort="Kang, Seunghwa" uniqKey="Kang S" first="Seunghwa" last="Kang">Seunghwa Kang</name></region><name sortKey="Bader, David A" sort="Bader, David A" uniqKey="Bader D" first="David A." last="Bader">David A. Bader</name><name sortKey="Schaeffer, Stephen W" sort="Schaeffer, Stephen W" uniqKey="Schaeffer S" first="Stephen W." last="Schaeffer">Stephen W. Schaeffer</name><name sortKey="Tang, Jijun" sort="Tang, Jijun" uniqKey="Tang J" first="Jijun" last="Tang">Jijun Tang</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000661 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000661 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= CyberinfraV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= PMC:3160844
|texte= Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:21887219" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a CyberinfraV1
| This area was generated with Dilib version V0.6.25. |  |